package demo.DataStrucAndAlgo.Linked;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/23-07-23-13:15
 * @Description：demo.DataStrucAndAlgo  双向链表
 * 双向，是Node结点中多了一个pre用来存储上一个结点
 */
class DNode{      //节点类
    public int no;
    public String data;
    public DNode next;       //保存下一个结点
    public DNode pre;        //保存上一个结点
    public DNode(int no, String data){
        this.no = no;
        this.data = data;
    }

    @Override
    public String toString() {
        return "DNode{" +
                "no=" + no +
                ", data='" + data + '\'' +
                '}';
    }
}
class doubleLinkedList{       //双向-普通类-有头-循环
    private DNode root = new DNode(0,"");     //创建根节点
    public DNode getRoot(){
        return this.root;
    }
    public void add(DNode newNode){       //普通add：不按序号存储
        DNode temp = this.root;          //root不能动，需要辅助结点
        while(temp.next!= null){
            temp = temp.next;       //向后移位
        }
        temp.next = newNode;       //尾结点双向添加
        newNode.pre = temp;
    }
    public void addByOrder(DNode newNode){    //按顺序add
        DNode temp = root;
        boolean flag = false;     //是否为重复编号
        while(temp.next != null){      //找到链表最后一位
            if(temp.next.no > newNode.no){       //找到合适位置（升序）
                break;
            }
            if(temp.next.no == newNode.no){     //找到重复编号
                flag = true;
                break;
            }
            temp = temp.next;       //向后一位
        }
        if(flag){
            System.out.println("查找到重复数据，无法加入");
            return;
        }else{
            //插入新节点
            newNode.next = temp.next;
            temp.next = newNode;
            if(temp.next !=null){   //若处于链尾时，next为空没有pre不能先前连，否则会空指向异常
                temp.next.pre = newNode;
            }
            newNode.pre = temp;
        }
    }
    public void show(){
        if(root.next == null){           //判断是否为空链表
            System.out.println("链表为空！");
            return;
        }
        DNode temp = root;
        while(temp.next != null){        //遍历打印
            System.out.println(temp.next.toString());
            temp = temp.next;
        }
    }
    public void modify(DNode newNode){        //根据DNode中的no来匹配要修改的结点
        DNode temp = root;
        boolean flag = false;            //判断是否找到了序号一样的DNode
        while(temp.next != null){       //遍历链表
            if(temp.next.no == newNode.no){       //找到序号一样的
                flag = true;
                break;
            }
            temp = temp.next;    //后移一位
        }
        if(flag){
            temp.next.data = newNode.data;
        }else{
            System.out.println("没有找到要修改的结点");
        }
    }
    public void remove(int no){     //删除结点
        DNode temp = root;      //这里是头结点，所以temp.next = temp.next.next没问题，如果不是头结点而是root.next,需要进行空判断
        boolean flag = false;    //判断是否找到了序号一样的DNode
        while(temp.next != null){
            if(temp.next.no == no){      //找到序号相等的结点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            DNode node = temp.next;
            temp.next = node.next;   //删除正向连接,这里不会空指向异常，因为有空的头结点
            if(node.next != null){     ////删除逆向连接，需要空判断
                node.next.pre = temp;
            }

        }else{
            System.out.println("没有找到要删除的结点");
        }
    }
    public void reverseShow(){    //逆向打印
        if(root.next == null){
            System.out.println("当前链表为空");
            return;
        }
        DNode temp = root;
        while(temp.next != null){     //找到最后一个结点
            temp = temp.next;
        }
        while(temp != root){        //逆向打印
            System.out.println(temp.toString());
            temp = temp.pre;
        }
    }
}
public class Double_Linked {
    public static void main(String[] args) {
        doubleLinkedList dlink=new doubleLinkedList();
        dlink.addByOrder(new DNode(1,"one"));
        dlink.addByOrder(new DNode(4,"three"));
        dlink.addByOrder(new DNode(2,"two"));
        dlink.addByOrder(new DNode(3,"three"));
        System.out.println("按顺序add：");
        dlink.show();

        System.out.println("修改结点：");
        dlink.modify(new DNode(4,"four"));
        dlink.show();

        System.out.println("删除结点：");
        dlink.remove(4);
        dlink.show();

        System.out.println("逆向打印：");
        dlink.reverseShow();

    }
}
